#include<bits/stdc++.h>//BAONI-40
using namespace std;
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); }
	while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	x = f ? -x : x;
	return ;
}

int t;
long long int k;
int n,m;
int ans;
long long int F[2000];

long long int C(int x,int y)
{
	if(F[y]*F[x-y])return F[x]/(F[y]*F[x-y]);
	return -1;
}

int main()
{
	freopen("problem.in","r",stdin);
	freopen("problem.out","w",stdout);
	read(t);read(k);
	F[0]=1;
	for(int i=1;i<=2000;++i)
		F[i]=F[i-1]*i;
	F[0]=0;
	while(t--)
	{
		read(n);read(m);
		ans=0;
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=min(i,m);++j)
			{
				if(!(C(i,j)%k))ans++;
			}
		}
		printf("%d\n",ans);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
